As the popularity of the Internet has grown so has the number of networks utilizing the Transmission Control Protocol/Internet Protocol (TCP/IP) for inter-processor communications. In fact, the popularity of TCP/IP has led to many internal networks (or intra-nets) being based upon this industry standard. TCP/IP is a connection-less best-efforts protocol which does not utilize any specific predetermined path from a message source to the message destination. One advantage of TCP/IP is that it may be utilized across any number of network architectures. Examples of architectures on which TCP/IP may be used include ethernet, System Network Architecture (SNA), token-ring, AppleTalk or others.
In TCP/IP, messages are typically routed based upon a destination address contained in the message. A message may take any path to the destination which is available. The message may also contain the address of the source of the message but typically does not contain the address of the devices in the path from the source to the destination. These addresses are typically determined by each device in the path based upon the destination address and the paths available. Thus, while the source and the destination of a message may be known, the route the message takes from the source to the destination may not be known.
FIG. 1 illustrates a possible interconnection of networks utilizing TCP/IP. As seen in FIG. 1, a number of TCP/IP networks 10, 12, 14 and 16 are interconnected through routing devices 20, 22, 24 and 26 which are connected through a network 18. When workstation 28 on network 10 sends a TCP/IP message (a "datagram") to a device outside of network 10, routing device 20 forwards the datagram to the network of the destination device.
Routing device 20 forwards the datagram based upon a destination address contained in the datagram by looking up in a routing table the address of the device where the datagram is to be sent. This routing table associates destination addresses with the addresses of accessible devices including routing information to the address provided in the datagram. Thus, in the interconnected networks illustrated in FIG. 1, if the datagram from workstation 28 has a destination address specifying workstation 30, then routing device 20 may direct the datagram to routing device 24 over network 18 which in turn would route the datagram over network 14 to workstation 30.
Each step in the path of the datagram from workstation 28 is commonly referred to as a "hop." A routing table typically specifies the address of the next hop in a datagram's path based upon the destination address of the datagram. Thus, the routing table includes the address of accessible devices to the routing device and the destination addresses which are associated with those accessible devices. Also, while the TCP/IP datagram may contain the source and destination addresses it does not necessarily contain the addresses of the route the datagram takes. Thus, the address of the device from which the previous hop originated may not be known to the next device in the route.
The manner in which a routing table is utilized by a routing device is commonly known as a "routing algorithm." In TCP/IP the routing algorithm is typically a three step process where the first step is to determine from the destination IP address of a datagram whether the address appears among the direct routes (host devices or networks which are accessible to the routing device without going through another routing device) specified in the routing table. If such is the case, then the datagram is sent to the directly attached network device. If the destination address does not specify a direct route, then the routing device determines if an indirect route (a route through a gateway to a device or network not directly accessible to the routing device) is specified for the destination address. If such is the case then the datagram is forwarded to the specified gateway IP address. Finally, if no direct or indirect route is specified then the datagram may be sent to a default address or, if no default address is specified, an error message returned to the source.
The routing tables used by routing devices in TCP/IP networks may be arrived at in a number of ways. In one type of routing, a routing table is broadcast to each routing device from a device which maintains a routing table of all possible routes. In other forms of routing, each routing device builds a routing table via its own dialogue which is called the routing protocol. These tables are then built and maintained by each routing device. In a third form of routing a fixed or static routing table is used for each message routed. Each of these cases has its own disadvantages. For example, the broadcast of a routing table or the routing protocol is typically repeated on a routine basis to assure that the routing device has an accurate routing table thereby using up network bandwidth. The static routing table, while not requiring network bandwidth, may be inefficient in determining the optimal routing path, may require frequent manual intervention or, in a worst case, be unable to adapt to changes in the network topography which make routes unavailable.
With respect to the dynamic routing methods, as the number of interconnected networks and the number of devices connected to those networks increases the size of the routing table, and, therefore, the amount of network resources occupied to maintain the routing table also typically increases. While the increase in resource utilization by an overhead process for establishing a routing table in each routing device may not present problems in many networks, in certain circumstances this overhead may occupy so much of the resources of the network as to cause unacceptable reductions in network performance. For instance, where a large number of TCP/IP networks are interconnect by an any-to-any network, such as an SNA network, the routing table broadcast to each of the routing devices may be so large as to occupy a significant portion of the SNA network's bandwidth. One example of such a network may be a large retail chain where each store in the chain has a TCP/IP network of the cash registers and other workstations located at the store and where each store in the chain is interconnected by an SNA network. In such an example, the any-to-any connectivity of the SNA network may create so large a routing table that the repeated broadcast of routing tables affects network performance.
In view of the above discussion, there exists a need for improvement in the routing of communications through large interconnected networks. In particular, improvements in the distribution and utilization of routing tables are needed so as to improve the performance of highly interconnected networks.